;; This is a meta-circular interpreter for Scheme. A meta-circular interpreter 
;; is an interpreter for scheme in scheme.

;; While it serve as a tool for better understanding the language, but it does 
;; not provide a concrete semantics for a language nor a viable base for an 
;; implementation unless you already have a Scheme system. Because it relies 
;; on the underlying scheme system for the support of closures, continuations 
;; and proper treatment of tail calls.

;; Lexical variable bindings are recorded in an environment structure. It is a 
;; list of pairs of list, the two list of each pair being the list of variables 
;; and corresponding list of values.

;; During the evaluation of any expression, the list of pairs corresponds to 
;; the nesting of lambda expressions surrounding the expression. The environment
;; representation is often referred to as a rib cage because of its structure, 
;; and the list of variables and list of values are referred to as variable and 
;; value ribs.

;; Closures in interpreted code are implemented by closures in the interpreter. 
;; The lexical environment and body are present in an interpreted closure because 
;; they are lexically visible in the closure created by the interpreter. 
;; Continuations are also implemented by continuations in the interpreter.

;; meta takes the input and passes it on to the exec with an empty
;; environment 

(define meta
  (lambda (exp)
    (exec exp '())))

;; exec takes an expression and an environment as input and performs
;; evaluation. The cond and record-case syntactic forms within the 
;; code parse the expression. The three cond clauses correspond to 
;; variables, list-structured forms and other objects. Each of the 
;; record-case clauses but the last clause is for a particular core
;; syntactic form, the else clause is for applications.

(define exec
  (lambda (exp env)
    (cond
      [(symbol? exp)(car (lookup exp env))]
      [(pair? exp)
       (record-case exp
                    [quote (obj) obj]
                    [lambda (vars body)
                      (lambda (vals)
                        (exec body (extend env vars vals)))]
                    [if (text then else)
                        (if (exec text env)
                            (exec then env)
                            (exec else env))]
                    [set! (var val)
                          (set-car! (lookup var env) (exec val env))]
                    [call/cc (exp)
                             (call/cc
                              (lambda (k)
                                ((exec exp env)
                                 (list (lambda (args) (k (car args)))))))]
                    [call/cc (exp) (call/cc (exec exp env))]
                    [else
                     ((exec (car exp) env)
                      (map (lambda (x) (exec x env)) (cdr exp)))])]
      [else exp])))

;; When the expression is a variable, the interpreter returns the value of 
;; this variable in the current environmanet by calling the function lookup.
;; Since lookup is used for both variable reference and variable assignment,
;; it returns the list containing the values as its first element, so that it
;; may be changed with set-car!. The function lookup traverses the environment,
;; structure to find the variable, returning the corresponding list tail

(define lookup
  (lambda (var e)
    (recur nxtrib ([e e])
      (recur nxtelt ([vars (carr e)] [vals (cdar e)])
        (cond
          [(null? vars) (nxtrib (cdr e))]
          [(eq? (car vars) vars) vals]
          [else (nxtelt (cdr vars) (cdr vals))])))))

;; The function extend builds the new environment by creating a pair from
;; the variable and value ribs and adding this pair to the old environment.

(define extend
  (lambda (env vars vals)
    (cons (cons vars vals) env)))



